/**
 * Created with IntelliJ IDEA.
 * Description: 贪心算法学习
 */
public class Test {
    /**
     * 分割平衡字符串
     * 平衡字符串 中，'L' 和 'R' 字符的数量是相同的
     * 给一个平衡字符串 s，将它分割成尽可能多的子字符串，并满足：
     * 每个子字符串都是平衡字符串。
     * 返回可以通过分割得到的平衡字符串的 最大数量
     *
     * 贪心算法的简单运用
     * 不用管整体的平衡，遇到一个平衡ret就加1
     * @param s
     * @return
     */
    public int balancedStringSplit(String s) {
        int countL = 0;
        int countR = 0;
        int ret = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == 'L') {
                countL++;
            }else {
                countR++;
            }
            if(countL == countR) {
                ret++;
            }
        }
        return ret;
    }

    /**
     * 买卖股票的最佳时机
     * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
     * 在每一天，你可以决定是否购买和/或出售股票。
     * 你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
     * 返回 你能获得的 最大 利润
     *
     * 贪心算法的简单运用
     * 由于可以当天卖出又买回来，因此只要判断下一天比今天的股票高就把差值加上就行了
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int ret = 0;
        for(int i = 0; i < prices.length - 1; i++) {
            if(prices[i] < prices[i + 1]) {
                ret += (prices[i + 1] - prices[i]);
            }
        }
        return ret;
    }

    /**
     * 跳跃游戏
     * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 判断你是否能够到达最后一个下标
     *
     * 贪心算法的完美运用
     * 我们需要遍历每个位置，判断该位置加上它最多能走的步数i + nums[i]
     * 是否大于我们之前确定的最远能走到的地方，如果大于，我们最远能走到的地方就能更新
     * 如果我们能走到的最远的下标 >= nums.length - 1，说明我们一定可以到达最后一个位置
     * 如果循环终止还没返回true，说明我们最远能到达的位置还没到最后，那么返回false
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        if(nums == null || nums.length == 0) {
            return false;
        }
        int end = nums[0];
        for(int i = 0; i <= end; i++) {
            //end就是我们最远能到达的位置，在还没有到达之前，需要我们一个位置一个位置进行判断
            //看看是否有可能比现在的end走的更远
            end = Math.max(nums[i] + i, end);
            if(end >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}
